/**
 * 最长公共子序列--不连续子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 **公共子序列** 的长度。如果不存在公共子序列，返回 0 

一个字符串的 **子序列** 是指这样一个新的字符串：
它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。
 */
/**
 * dp[i][j]  text1[0,i-1] 与 text2[0,j-1] 的最长公共子序列为dp[i][j]
 * 更新两种状态：
 * （1）当前相同元素 dp[i][j] = dp[i-1][j-1] + 1
 * （2）😐当前元素不相同,取之前状态的最大值： dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
 * 
 * 对比
 * 连续：res = Math.max(res, dp[i][j]);
 * 不连续：dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); //往前推动
 */
var longestCommonSubsequence = function(text1, text2) {
  const [m,n] = [text1.length, text2.length];
  const dp = Array(m+1).fill().map(() => Array(n+1).fill(0));
  for(let i=1;i<=m;i++) {
    for(let j=1;j<=n;j++) {
      if(text1[i-1] === text2[j-1]) {
        dp[i][j] = dp[i-1][j-1]+1;
      } else {
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); //往前推动
      }
    }
  }
  return dp[m][n];
};
const text1 = "abcde";
const text2 = "ace" ;
console.log('最长公共子序列', longestCommonSubsequence(text1, text2)); //3